package puzzle.projecteuler.p200;

import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;
import astudy.util.Permutation;

public class Problem118C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();
		System.out.println(count());
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}

	public static int count() {
		
		int total = 0;
		List<List<Integer>> splits = split(9);
		int[] c = {1,2,3,4,5,6,7,8,9};
		Integer[] ps = null;
		while (c != null) {
			for (List<Integer> split: splits) {
				ps = new Integer[split.size()];
				int i = 0, start = 0, end = 0;
				for (int t: split) {
					end += t;
					ps[i] = 0;
					for (int j = start; j < end; j ++) {
						ps[i] = ps[i]*10 + c[j];
					}
					i ++;
					start += t;
				}
				//{2,5,47,89,631}和{5,2,47,89,631}其实是一样的。
				//为了避免重复计数，参与计数的集合必须满足：
				//1、按递增顺序排列
				//2、必须都是素数
				boolean allOrderedPrimes = true;
				for (int j = 1; j < ps.length; j ++) {
					if (ps[j-1] > ps[j]) {
						allOrderedPrimes = false;
						break;
					}
				}
				if (allOrderedPrimes) {
					for (Integer p: ps) {
						if (!AdvMath.isPrime(p)) {
							allOrderedPrimes = false;
							break;
						}
					}
				}
				if (allOrderedPrimes) {
					total ++;
				}
			}
			c = Permutation.next(c);
		}
		return total;
	}
	
	/**
	 * 将m分解成不同自然数和的所有方式
	 * @param m
	 * @return
	 */
	public static List<List<Integer>> split(int m) {
		
		List<List<Integer>> rs = new ArrayList<List<Integer>>();
		if (m == 0) {
			List<Integer> tmp = new ArrayList<Integer>();
			rs.add(tmp);
		} else {
			for (int f = 1; f <= m; f ++) {
				List<List<Integer>> tmp = split(m-f);
				for (List<Integer> l: tmp) {
					//为了减少重复数据，限制所有的乘数必须按降序排列
					boolean g = true;
					for (Integer a: l) {
						if (a > f) {
							g = false;
							break;
						}
					}
					if (g) {
						List<Integer> newl = new ArrayList<Integer>();
						for (Integer a: l) {
							newl.add(a);
						}
						newl.add(f);
						rs.add(newl);
					}
				}
			}
		}
		return rs;
	}
}
